In a game like Dominoes or Tic-Tak-Toe , or Bridge and Chess or even a simulator , a Rpg or an adventure etc. how does the computer "MAKE ITS MOVE".
I mean the Computer just "knows" a set (list) of allowed possible future moves to make but how is the BEST of them choosen?(in the long term its even more difficult)
i think of it like an example of a maze. when we were children we tryed to find the exit by drawing along the path wich was "nearer in sight" and if it was wrong we draw backwards till the first "crossing" and draw the other way along.
Q: The "game" should search in the "LIST OF ALLOWED MOVES" for ALL the solutions and store them in ....? another list? and then create anoter LIST OF ALLOWED MOVES (for each possible move?) and how is the list "UPDATED" after each possible move and after each HUMAN move? (deleting it each time and re-creating it is ofcourse programming failure)?
So there is a LIST OF LISTS and the smaller which finds a BETTER GOAL is the best? (if you cant win just make a DRAW)
PS: sorry my english is not so good and the subject is messing me.
(deleting it each time and re-creating it is ofcourse programming failure)?
I think it comes down to making a list of all possible moves and weighting them for probability of success. You would probably make a hierarchical structure (linked list -> binary tree) and drop the first level in the hierarchy and the branch that did not apply on each move. But this is just a guess.
I´m not into AI programming (yet), but i found the programming articles and tutorials on this site to be great. On the first glance, they also offer some (good?) articles on AI programming and different algorithms:
since the readings are quite many but noone anwsers i write my code down ....
well its not at any means correct and since i use C++ and its a general algorithm i think its the correct forum, else im sorry in advance and the mod please (if possible) move the threat to the C forum!
class Node
{
int Data;
Node *nextmove;
List Listofmoves;
public :
Node () {Data=0; nextmove=0; }
Node (int d , Node *n) {Data=d, nextmove=n; }
~Node () {}
friend class List;
friend List move(List);
};
class List
{
Node *Head;
Node *Last;
Node *Now;
public :
List () ;
~List () ;
List & append(int);
List & next();
int find_move(List);
friend List move (List);
friend class Node;
};
List :: List ()
{ Head=0; Last=0; Now=0;}
List :: ~List () {}
List & List :: append(int i)
{
if (Head==0)
{
Head = new Node(i,Last);
Last= Head;
}
else
{
Last = new Node(i,Last);
}
return *this;
}
List & List :: next ()
{ if ( Now !=0 ) Now = Now->nextmove; return *this; }
int List :: find_move(List l)
{ l.next(); return l.Now->Data; }
List move (List listl)
{
if (listl.Last!=0)
move(listl.append(listl.find_move(listl.Last.Listofmoves)));
else
return(listl.Push_in_list_of_goaling_Lists);
}
All the "check" is done in the recursive function MOVE.
I want to ADD to A List OF POSSIBLE MOVES the element of a List OF NEXT MOVES from the LAST element OF THE List OF POSSIBLE MOVES.
AT the end the output is stored in a 3rd List and then the List of the Lists that have the desired goal are check 1 by 1 for the best solution.
any comment or idea appritieted.
I think I see what you're saying here. I actually used something slightly similar when I wrote a chess program a long time ago. The way I recall it, I had a board class that stored the position of all the pieces as well as a push down list for adding moves to it. I had a copy constructor so I could copy a board position. I would pass the current board position to the move() function. The move() function would loop through all the possible moves a side could make and generate the new board positions. It would recursively call itself for each one of these positions and pass the new board position. I did this for a depth of 2, 4 or 6 (depending on the difficulty setting), so that it would generate moves for both sides. When the function recursed to the max depth, I pushed the final board class structure into the linked list (not the intermediate positions, since they're stored as part of the push list in the board class structure). Then I would evaluate the final positions from the list and decide which was the best position to get to. Then I would use that push list that was part of the board structure and make that move.
Here's my pseudo-C++ code for that. Hope this helps :)
class Board() {
public:
char positions[80];
Board() { movelist = NULL; }
Board(const board& p); // Copy constructor
Node *movelist;
AddMove( Move *move);
RemoveMove(); // Pops the last move
};
// If max depth is reached, push this board class into a stack
if (depth == max_depth) {
push_position_stack(b);
return;
}
for (int i=1; i < 80; i++)
if temp.positions[i] { // if something is there at this position
gen_move(side, temp, i, movelist); // Generate all moves for this piece
// Now go through all the moves for this piece
for (int j=0; j < movelist->count; j++) {
move = movelist[j];
// Add this move to the board
temp.AddMove(move);
// Recurse into make move for the other side)
make_move(1 - side , b, depth++);
// Remove the last move and evaluate next possible move
temp.RemoveMove()
}
}
I am not 100% sure what the original question was, but from my understanding of it, here is my answer from my own experience with AI programming:
- AI engines choose their move by assigning a value to each move. This value for each move needs no other meaning other than a move that is better than another move should have a higher value. The computer picks the move with the highest value.
How does it value each move?
The way the computer assigns values to its moves is with a game tree. It takes the current position, and makes all possible moves on it, and then makes all possible moves on each of these positions, and so on (via recursion) until it runs out of time. At the end of this game tree is all possible positions the computer has analyzed. Let's say it has enough time to compute 8 ply ahead, then the positions at the end of the tree are all possible positions after 4 moves for each side. The computer gives a value to all of these positions. Assuming both sides play perfectly, it picks the original move that results in the highest value of these ending positions.
Here is a great page that better explains my rather poor attempt:
http://www.xs4all.nl/~verhelst/chess/search.html
For the other things that have been mentioned in this thread:
- For a chess engine, the best way to create all of these positions in a game tree, is to move as less memory as possible. This means you should not copy an entire position so that you can make a move on it. Store only the information that you need to make and un-make the move. This means more processing (i.e. more coding), but it means less memory is being moved, so it is faster.